<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    // 封装二叉搜索树
    function BinarySerachTree() {

        function Node(key) {
            this.key = key
            this.left = null
            this.right = null
        }

        //属性
        this.root = null

        // 方法
        // 插入数据
        BinarySerachTree.prototype.insert = function (key) {
            // 1.根据key创建节点
            var newNode = new Node(key)

            // 2.判断有没有根节点
            if (this.root == null) {
                this.root = newNode
            } else {
                this.insertNode(this.root, newNode)
            }
        }

        BinarySerachTree.prototype.insertNode = function (node, newNode) {
            if (newNode.key < node.key) {
                // 向左查找
                if (node.left == null) {
                    node.left = newNode
                } else {
                    this.insertNode(node.left, newNode)
                }
            } else {
                // 向右查找
                if (node.right == null) {
                    node.right = newNode
                } else {
                    this.insertNode(node.right, newNode)
                }
            }
        }


        // 树的遍历
        // 1.先序遍历
        BinarySerachTree.prototype.preOrderTraversal = function (handler) {
            this.preOrderTraversalNode(this.root, handler)
        }

        BinarySerachTree.prototype.preOrderTraversalNode =function (node, handler) {
            if (node != null) {
                // 打印当前节点
                handler(node.key)

                // 遍历左子树
                this.preOrderTraversalNode(node.left, handler)
                // 遍历右子树
                this.preOrderTraversalNode(node.right, handler)
            }
        }

        // 1.中序遍历
        BinarySerachTree.prototype.midOrderTraversal = function (handler) {
            this.midOrderTraversalNode(this.root, handler)
        }

        BinarySerachTree.prototype.midOrderTraversalNode =function (node, handler) {
            if (node != null) {
                // 遍历左子树
                this.midOrderTraversalNode(node.left, handler)

                // 打印当前节点
                handler(node.key)

                // 遍历右子树
                this.midOrderTraversalNode(node.right, handler)
            }
        }

        // 后序遍历
        BinarySerachTree.prototype.postOrderTraversal = function (handler) {
            this.postOrderTraversalNode(this.root, handler)
        }

        BinarySerachTree.prototype.postOrderTraversalNode =function (node, handler) {
            if (node != null) {
                // 遍历左子树
                this.postOrderTraversalNode(node.left, handler)

                // 遍历右子树
                this.postOrderTraversalNode(node.right, handler)

                // 打印当前节点
                handler(node.key)
            }
        }

        // 寻找最值
        // 1.寻找最大值
        BinarySerachTree.prototype.max = function () {
            // 1.获取根节点
            var node = this.root
            while (node.right != null) {
                node = node.right
            }
            return node.key
        }

        // 2.寻找最小值
        BinarySerachTree.prototype.min = function () {
            var node = this.root
            while (node.left != null) {
                node = node.left
            }
            return node.key
        }


        // 搜索某一个key
        BinarySerachTree.prototype.search = function (key) {
            var node = this.root

            while (node != null) {
                if (node.key > key) {
                    node = node.left
                }else if (node.key < key) {
                    node = node.right
                }else {
                    return true
                }
            }
            return false
        }

        // 删除节点
        BinarySerachTree.prototype.remove = function (key) {
            // 1.定义临时保存变量
            var current = this.root
            var parent = this.root
            var isleftChild = true

            // 2.查找节点
            while (current.key != key) {
                parent = current
                if (key < current.key) {
                    isleftChild = true
                    current = current.left
                } else {
                    isleftChild = false
                    current = current.right
                }

                // 找到最后的节点依旧没有找到key
                if (current == null) return false

            }
            // 根据对应的情况删除节点
            // 如果删除节点为子节点
            if (current.left == null && current.right == null) {
                if (current == this.root) {
                    this.root = null
                } else if (isleftChild) {
                    parent.left = null
                } else {
                    parent.right = null
                }
            }

            // 如果删除节点一个子节点
            else if (current.left == null) {
                if (current == this.root) {
                    this.root = current.right
                } else if (isleftChild) {
                    parent.left = current.right
                } else {
                    parent.right = current.right
                }
            } else if (current.right == null) {
                if (current == this.root) {
                    this.root = current.left
                } else if (isleftChild) {
                    parent.left = current.left
                } else {
                    parent.right = current.left
                }
            }

            // 删除的节点有两个子节点
            else {
                // 1.获取后继节点
                var successor = this.getSuccessor(current)

                // 2.判断是否为根节点
                if (current == this.root) {
                    this.root = successor
                } else if (isleftChild) {
                    parent.left = successor
                } else {
                    parent.right = successor
                }

                successor.left = current.left
            }
        }


        // 寻找后记的方法
        BinarySerachTree.prototype.getSuccessor = function (delNode) {
            // 1.定义变量，保存找到的后继节点
            var successor = delNode
            var current = delNode.right
            var successorParent = delNode

            // 2.循环查找
            while (current != null) {
                successorParent = successor
                successor = current
                current = current.left
            }

            // 3.判断寻找的后继节点是否为delNode的right节点
            if (successor != delNode.right) {
                successorParent.left = successor.right
                successor.right = delNode.right
            }
            return successor
        }
    }



    // 测试
    var tree = new BinarySerachTree()

    // 1. 插入数据
    tree.insert(11)
    tree.insert(7)
    tree.insert(15)
    tree.insert(5)
    tree.insert(3)
    tree.insert(9)
    tree.insert(8)
    tree.insert(10)
    tree.insert(13)
    tree.insert(12)
    tree.insert(14)
    tree.insert(20)
    tree.insert(18)
    tree.insert(25)
    tree.insert(6)

    // 2.测试遍历
    // 测试先序遍历
    var resultString = ''
    tree.preOrderTraversal(function (key) {
        resultString += key + ' '
    })
    alert(resultString)

    // 测试中序遍历
    resultString = ''
    tree.midOrderTraversal(function (key) {
        resultString += key + ' '
    })
    alert(resultString)

    // 测试后序遍历
    resultString = ''
    tree.postOrderTraversal(function (key) {
        resultString += key + ' '
    })
    alert(resultString)

    // 4.测试最值
    // alert(tree.max())
    // alert(tree.min())

    // 5.搜索测试方法
    // alert(tree.search(25))
    // alert(tree.search(24))
    // alert(tree.search(2))

    // 6.测试删除代码
    tree.remove(9)
    tree.remove(7)
    tree.remove(15)
    resultString = ''
    tree.postOrderTraversal(function (key) {
        resultString += key + ' '
    })
    alert(resultString)

</script>
</body>
</html>
